๐Ÿ’ก ๋‹ค์ต์ŠคํŠธ๋ผ(Dijkstra) ์•Œ๊ณ ๋ฆฌ์ฆ˜

@Seongukbaek Posted May 13, 2022 ยท Updated May 13, 2022 ยท 4 min read

๐Ÿงท ๋‹ค์ต์ŠคํŠธ๋ผ(Dijkstra) ์•Œ๊ณ ๋ฆฌ์ฆ˜

DP๋ฅผ ํ™œ์šฉํ•œ ์ตœ๋‹จ ๊ฒฝ๋กœ ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ, ์‹œ์ž‘ ์ •์  s ์—์„œ๋ถ€ํ„ฐ ๋‹ค๋ฅธ ์ •์ ๋“ค๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์‚ฐํ•œ๋‹ค.

  • DP๊ฐ€ ์ ์šฉ๋˜๋Š” ์ด์œ ๋Š”, ๊ตณ์ด ํ•œ ๋ฒˆ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•œ ๊ณณ์€ ๋‹ค์‹œ ๊ตฌํ•  ํ•„์š”๊ฐ€ ์—†๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.
  • ๊ทธ๋ฆฌ๊ณ  ์ด๋ฅผ ํ™œ์šฉํ•ด ์ •์ ์—์„œ ์ •์ ๊นŒ์ง€ ๊ฐ„์„ ์„ ๋”ฐ๋ผ ์ด๋™ํ•  ๋•Œ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ํšจ์œจ์ ์œผ๋กœ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

๊ฐ„์„ ์˜ ๊ฐ’์ด ์–‘์ˆ˜์ธ ๊ฒฝ์šฐ๋งŒ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.

์Œ์ˆ˜ ๊ฐ„์„ ์ด ์กด์žฌํ•˜๋ฉด ์•ˆ๋˜๋Š” ์ด์œ ?

  • ์œ„ ๊ฒฝ์šฐ, A์—์„œ ์ถœ๋ฐœํ•˜์—ฌ dist[B] = 10 , dist[C] = 4 ๋กœ ์—…๋ฐ์ดํŠธํ•œ ํ›„,
  • ๊ฐ€์žฅ ๋น„์šฉ์ด ์ž‘์€ C๋กœ ์ด๋™ํ•  ๊ฒƒ์ด๋‹ค. ๊ทธ๋ ‡๊ฒŒ ๋˜๋ฉด, ๋” ์ด์ƒ C์˜ ๊ฑฐ๋ฆฌ๊ฐ€ ๊ฐฑ์‹ ๋  ์ผ์ด ์—†์–ด -90์ด ์•„๋‹Œ 4๋กœ ์ข…๋ฃŒ๋œ๋‹ค.

ํ•˜์ง€๋งŒ, ์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ์‚ฌ์šฉํ•ด ๋ฐฉ๋ฌธํ•œ ์ •์ ์— ๋Œ€ํ•ด์„œ ์žฌ๋ฐฉ๋ฌธํ•˜์—ฌ ์ตœ์†Œ ๋น„์šฉ์„ ์ €์žฅํ•œ๋‹ค๋ฉด ์Œ์ˆ˜ ๊ฐ€์ค‘์น˜์— ๋Œ€ํ•œ ๊ณ„์‚ฐ์ด ๊ฐ€๋Šฅํ•˜๋‹ค. ์ด๋Š” ์•„๋ž˜์—์„œ ๊ตฌํ˜„ํ•œ๋‹ค.

๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๊ตฌํ˜„์„ ์œ„ํ•ด 2๊ฐ€์ง€๋ฅผ ์ €์žฅํ•ด์•ผ ํ•œ๋‹ค.

  • ํ•ด๋‹น ์ •์ ๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ
  • ์ •์  ๋ฐฉ๋ฌธ ์—ฌ๋ถ€

๐Ÿชš ๊ณผ์ •

  1. ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ๊ฐ’์€ ๋ฌดํ•œ๋Œ€ ๊ฐ’์œผ๋กœ ์ดˆ๊ธฐํ™”
  2. ์‹œ์ž‘ ์ •์ ์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋Š” 0์ด๋‹ค. (๋ฐฉ๋ฌธ ์ฒ˜๋ฆฌ)
  3. ์‹œ์ž‘ ์ •์ ๊ณผ ์—ฐ๊ฒฐ๋œ ์ •์ ๋“ค์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ๊ฐ’์„ ๊ฐฑ์‹ 
  4. ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ •์  ์ค‘ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๊ฐ€ ์ตœ์†Œ์ธ ์ •์ ์„ ํƒ์ƒ‰
  5. ์ฐพ์€ ์ •์ ์„ ๋ฐฉ๋ฌธ ์ฒดํฌํ•˜๊ณ , ํ•ด๋‹น ์ •์ ๊ณผ ์—ฐ๊ฒฐ๋œ ๋ฏธ๋ฐฉ๋ฌธ ์ •์ ์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ๊ฐ’์„ ๊ฐฑ์‹ 
  6. ๋ชจ๋“  ์ •์ ์„ ๋ฐฉ๋ฌธํ•  ๋•Œ๊นŒ์ง€ 4~5๋ฒˆ ๋ฐ˜๋ณต

๐Ÿชš ์‹œ๊ฐ„ ๋ณต์žก๋„

  • ์ธ์ ‘ ํ–‰๋ ฌ ๊ตฌํ˜„ ์‹œ: O(N2)O(N^2)
  • ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ ๊ตฌํ˜„ ์‹œ: O(NlogN)O(NlogN)

๐Ÿชš ์ผ์ข…์˜ ๊ฐœ์„ ?

์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ์‚ฌ์šฉํ•ด ๊ฑฐ๋ฆฌ๊ฐ€ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์ •์ ๋ถ€ํ„ฐ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋„๋ก ํ•œ๋‹ค.

  • ์šฐ์„ ์ˆœ์œ„ ํ์— ์ •์ ์˜ ๋ฒˆํ˜ธ์™€ ์ง€๊ธˆ๊นŒ์ง€ ์ฐพ์•„๋‚ธ ํ•ด๋‹น ์ •์ ๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ์Œ์œผ๋กœ ์ €์žฅํ•œ๋‹ค.
  • ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ •์  ์ค‘ ์‹œ์ž‘์ ์œผ๋กœ๋ถ€ํ„ฐ์˜ ๊ฑฐ๋ฆฌ๊ฐ€ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์ ์„ ์ฐพ๋Š” ๊ณผ์ •์„ ๊ฐ„๋‹จํ•˜๊ฒŒ ํ•ด์ค€๋‹ค.

์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ์‚ฌ์šฉํ•œ๋”ฐ๋Š” ์ ์„ ์ œ์™ธํ•˜๋ฉด, BFS์™€ ๋น„์Šทํ•œ ๊ตฌ์กฐ์˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

  • ๊ฐ ์ •์ ๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ์ €์žฅํ•˜๋Š” ๋ฐฐ์—ด์„ ์œ ์ง€ํ•˜๋ฉฐ,
  • ์ •์  ๋ฐฉ๋ฌธ๋งˆ๋‹ค ์ธ์ ‘ํ•œ ์ •์ ์„ ๋ชจ๋‘ ๊ฒ€์‚ฌํ•œ๋‹ค.
class Pair implements Comparable<Node> { int num; int weight; public Pair(int num, int weight) { this.num = num; this.weight = weight; } @Override public int compareTo(Node n) { return this.weight - n.weight; } } int V; ArrayList<ArrayList<Pair>> adjList = new ArrayList<>(); int[] dijkstra(int src) { int[] dist = new int[V]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0; Queue<Pair> queue = new PriorityQueue<>(); queue.add(new Pair(src, 0)); while(!queue.isEmpty()) { Pair p = queue.poll(); int here = p.num; int cost = p.weight; if (dist[here] < cost) continue; for (int i = 0; i < adjList.get(here).size(); i++) { int there = adjList.get(here).get(i).num; int nextDist = cost + adjList.get(here).get(i).weight; if (dist[there] > nextDist) { dist[there] = nextDist; queue.add(new Pair(there, nextDist)); } } } }

๐Ÿ“• ์ฐธ๊ณ 

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€